1. Field of the Invention
This invention relates to the field of circuit design and, more particularly, to the use of analytical placement to optimize placement of components for a given design.
2. Description of the Related Art
Efficiently and optimally placing components on a device for a given mapped design and a given device continues to be a challenge as designs become ever increasingly complex. The placement problem forces a decision as to where or which sites on the device the components from the design should be placed. Analytical placement is one solution for the placement problem. In analytical placement, the placement problem is typically formulated as a problem of minimizing an equation that represents some goodness-of-placement metric. Variables in this equation correspond to the locations of components to be placed. Typical goodness-of-placement metrics might attempt to estimate the total amount of wirelength that would be needed to connect the components as specified by the design. Thus, the placement problem is reduced to finding a set of variable values (i.e., component placements) that minimize the value of the equation (i.e., optimize for whatever metrics are represented by the equation). In general, the solution to the minimization problem provides a set of real-valued locations that do not map directly to discrete sites into which components can be placed, but instead to an abstract two-dimensional location space that covers the device. Thus, the real-valued locations for components resulting from the solution of the minimization problem must be discretized into a set of specific device sites into which components can be placed, resolving any overlap that may arise due to multiple real-valued locations falling within the area that would most naturally map to a particular site. One approach to resolving such overlap issues employs an iterative scheme in which the system of equations is repeatedly incrementally modified to introduce “spreading forces” that attempt to push components away from oversubscribed areas and toward undersubscribed areas. This iterative approach generally works well as long as there are no significant restrictions on where individual components can or must be placed.
Traditionally, analytical placement assumes a homogeneous substrate in which any component from the design can, in effect, be placed at essentially any location on the device (modulo discretization of the real-valued locations to specific device sites). However, the assumption of a homogeneous substrate fails to hold true for some recent FPGA families. In particular, some recent FPGA devices can have features like CPU cores (which leave a large “hole” in the real-valued location space into which no other component types can be placed) and BlockRAMs and multipliers (which can only be placed in a relatively small number of device sites, effectively causing a large fraction of the real-valued location space to be made up of “holes” into which components of those types cannot be placed). Thus, analytical placement may yield infeasible locations. In other words, analytical placement yields real-valued locations for components that have no directly-corresponding device site at which the component could be placed (e.g., due to a “hole” in the device fabric to accommodate a large block such as a CPU core that precludes placement of any other component types or due to a component type that can only be placed at one of a relatively small number of locations on the device). In such a scenario, the discretization process may yield actual placements that are significantly different from the solution suggested by the analytical placement process. Existing approaches attempt to address these problems a posteriori, by introducing “spreading forces” (as described above) that attempt to move components away from infeasible locations and towards feasible locations in which they could actually be placed. No known existing approaches to the placement problem attempt to address these problems a priori.